package 剑指II;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-11-05
 **/

public class Jz019最多删除一个字符得到回文 {

    /**
     * 给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。
     * <p>
     * 示例 1:
     * 输入: s = "aba"
     * 输出: true
     * 示例 2:
     * 输入: s = "abca"
     * 输出: true
     * 解释: 可以删除 "c" 字符 或者 "b" 字符
     * 示例 3:
     * 输入: s = "abc"
     * 输出: false
     *  
     * 提示:
     * 1 <= s.length <= 105
     * s 由小写英文字母组成
     */

    public boolean validPalindrome(String s) {

        char[] arr = s.toCharArray();
        int left = 0;
        int right = s.length() - 1;

        while (left <= right) {
            char lC = arr[left++];
            char rC = arr[right--];
            if (lC != rC) {
                return this.validPalindrome(arr, left - 1, right) || this.validPalindrome(arr, left, right + 1);
            }
        }

        return true;
    }

    private boolean validPalindrome(char[] arr, int left, int right) {
        while (left <= right) {
            char lC = arr[left++];
            char rC = arr[right--];
            if (lC != rC) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Jz019最多删除一个字符得到回文 n = new Jz019最多删除一个字符得到回文();
        boolean result = n.validPalindrome("abca");
    }

}
